package priotityqeue;

import java.util.Arrays;

public class Heap {

    //向下调整（小堆）
    //array 要调整的堆
    //index 要调整的位置
    public static void shiftDown(int[] array, int size,int index) {
        //要调整的父节点
        int parent= index;
        //计算要调整的左孩子节点
        int child=2*parent+1;
        //如果子节点超出范围，说明子节点不存在
        //主循环结束，调整完成
        while(child<size){
            //如果右子树比左子树小，则定位到右子树
            if(child+1<size && array[child]>array[child+1]){
                child=child+1;
            }
            //然后比较child与parent的大小
            if(array[parent]<=array[child]){
                break;
            }else{
                //如果parent大于child，则交换两者的值
                int temp=array[parent];
                array[parent]=array[child];
                array[child]=temp;
                //更新parent和child的值
                parent=child;
                child=2*parent+1;
            }
            }
            }

            //向上调zheng 整个数组只有最后一个元素不满足堆结构，所以从最后一个元素开始向上调整
             public static void shiftUp(int[] array, int index){
                 int child=index;
                 int parent = (child-1)/2;
                 while(child>0){
                     //如果parent大于child，则交换两者的值
                     if(array[parent]>array[child]){
                         int temp=array[parent];
                         array[parent]=array[child];
                         array[child]=temp;
                         //更新parent和child的值
                         child=parent;
                         parent=(child-1)/2;
                     }else{
                         break;
                     }

                 }
             }

            //创建的堆
            public static void createHeap(int[] array){
            //找到最后一个非叶子节点，从后从后往前向下调整
               int lastLeaf=array.length-1;
               int lastparent=(lastLeaf-1)/2;
               for(int i=lastparent;i>=0;i--){
                   shiftDown(array,array.length,i);
               }
            }
    public static void main(String[] args) {
        int[] array={4,2,7,1,3,9,8,5,6};
        createHeap(array);
        System.out.println(Arrays.toString(array));
    }
        }

